This description relates to an approach to compiling graph-based program specifications.
One approach to data flow computation makes use of a graph-based representation in which computational components corresponding to nodes (vertices) of a graph are coupled by data flows corresponding to links (directed edges) of the graph (called a “dataflow graph”). A downstream component connected to an upstream component by a data flow link receives an ordered stream of input data elements, and processes the input data elements in the received order, optionally generating one or more corresponding flows of output data elements. A system for executing such graph-based computations is described in prior U.S. Pat. No. 5,966,072, titled “EXECUTING COMPUTATIONS EXPRESSED AS GRAPHS,” incorporated herein by reference.
Dataflow graphs are often specified such that there is a possibility that two or more components can execute concurrently (i.e., in parallel). Many systems for compiling and executing dataflow graphs capitalize on the possibility of concurrency by compiling dataflow graphs such that the components of the dataflow graphs execute concurrently, where possible. By doing so, these systems focus on executing the dataflow graph with a minimal latency.